#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int getmaxprice(int n,int v,vector<int>& space,vector<int>& price){
    vector<vector<int>> dp(n+1,vector<int>(v+1));
    //dp[i][j] 表示在前i个物品，背包容量为j的最大容纳价值
    int ret = 0;
    for(int i = 1; i < n+1 ; i++){
        for(int j = 1; j < v+1 ; j++){
            //第i个物品选或者不选
            dp[i][j] = j >= space[i] ? max(dp[i-1][j-space[i]]+price[i],dp[i-1][j]) : dp[i-1][j];
            ret = max(ret,dp[i][j]);
        }
    }
    return dp[n][v];
}
int completgetmaxprice(int n,int v,vector<int>& space,vector<int>& price){
    vector<vector<int>> dp(n+1,vector<int>(v+1));
    //dp[i][j] 表示在前i个物品，使用背包容量为j的最大容纳价值
    dp[0][0] = 0;
    for(int i = 1 ; i < v+1;i++){
        dp[0][i] = -1; //-1表示不能选出
    }
    for(int i = 1 ; i < n+1 ; i++){
        for(int j = 1 ; j <v+1 ; j++){

            if(dp[i-1][j-space[i]] != -1&&j >= space[i]){
                dp[i][j] = max(dp[i-1][j-space[i]]+price[i],dp[i-1][j]);
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n][v]==-1 ? 0 :dp[n][v] ;
}
int main(){
    int n = 0,v = 0;
    std::cin>>n>>v;
    std::vector<int> price(n+1);
    std::vector<int> space(n+1);
    for(int i = 1 ; i < n+1;i++){
        std::cin>>space[i]>>price[i];
    }
    cout<<getmaxprice(n,v,space,price)<<endl;
    cout<<completgetmaxprice(n,v,space,price)<<endl;
    
}